//单链表

#pragma once

//单链表类型定义

template <typename ElemType>
struct LNode
{
    ElemType data;
    LNode *next;
};

template <typename ElemType>
using LinkList = LNode<ElemType> *;


//初始化空表 InitList(&L)
template <typename ElemType>
void InitList(LinkList<ElemType> &L)
{
    L = new LNode<ElemType>;
    L->next = nullptr; // 0, null
}

//销毁单链表 DestroyList(&L)
template <typename ElemType>
void DestroyList(LinkList<ElemType> &L)
{
    while (L)
    {
        auto p = L;
        L = L->next;
        delete p;
    }
}


//单链表插入 ListInsert(&L,i,e)
template <typename ElemType>
void ListInsert(LinkList<ElemType> &L, int i, ElemType e)
{
    //找到第 i-1 个节点 p
    auto p = L;
    int j = 0;
    while (p && j<i-1){
        p = p->next; 
        j++;
    }
    
    //在 p 之后插入 e
    if (p && j==i-1){
        // auto s = new LNode<ElemType>
        // s->data = e;
        // s->next = p->next;
        // p->next = s;
        p->next = new LNode<ElemType> {e,p->next};
        
    }else{
        throw "i out of range";
    }
}

//单链表删除 ListDelete(&L,i&e)
template <typename ElemType>
void ListDelete(LinkList<ElemType> &L, int i, ElemType &e)
{
    //找到第 i-1 个结点 p
    auto p = L;
    int j = 0;
    while (p && j<i-1){
        p = p->next; 
        j++;
}

//删除第 i 个结点
if (p && j==i-1 && p->next){
        auto q = p->next;
        p->next = q->next;
        e = q->data;
        delete q;
    }else{
        throw "i out of range";
    }
}
